package leetcode.pre50;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 电话号码2对应abc,3对应def，...，9对应xyz。
 * 给一个数字字符串，输入所有可能的字母组合：如
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 *
 * 分析：这里其实就是排列组合问题。每个位置有k种可能，最后拼接。
 *
 * @date 2019/11/20 0020 下午 10:45
 */
public class Code17_PhoneNumCombination {
    private static final String[] Member = {
            " ",    //0 do not care what
            "",     //1 do not care what
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };

    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        //检测是否合法
        try {
            Integer.parseInt(digits);
        } catch (NumberFormatException e) {
            e.printStackTrace();
            return new ArrayList<>();
        }
        List<String> res = new LinkedList<>();
        //对digits做笛卡尔积
        process(digits,0,"",res);
        return res;
    }

    private static void process(String digits, int index, String curRes, List<String> res) {
        if(index == digits.length()){
            res.add(curRes);
            return;
        }
        //获取当前电话号码
        int num = digits.charAt(index) - '0';
        // 获取对应的要遍历的字母集合，如2 对应abc
        String target = Member[num];
        //对当前target进行遍历
        for (int i = 0; i < target.length(); i++) {
            String temp = target.substring(i,i+1);
            process(digits,index+1,curRes+temp,res);
        }
    }
    public static void main(String[] args) {
        List<String> list = letterCombinations("23");
        list.forEach(System.out::println);
    }
}
